package org.example.SolutionNew001;

import java.util.HashMap;
import java.util.Map;

public class SubString01 {
    public static void main(String[] args) {
        SubString01 s=new SubString01();
        int[] nums=new int[]{-1,-1,1};
        System.out.println(s.subarraySum(nums,0));

    }

    //子串题用什么滑动窗口啊，根本不一样T T
    public int subarraySum0(int[] nums, int k) {
        int n = nums.length;
        int res=0;
        int start=0,tmp=0;
        for(int i=0;i<n;i++){
            tmp+=nums[i];
            if(tmp==k){
                res++;
                tmp-=nums[start];
                start++;
            }else if(tmp>k){
                while(start<i&&tmp>k){
                    tmp-=nums[start];
                    start++;
                }
                if(tmp==k){
                    res++;
                    tmp-=nums[start];
                    start++;
                }
            }
        }
        return res;
    }

    public int subarraySum1(int[] nums, int k) {
        int n = nums.length;
        int res=0;
        for(int i=0;i<n;i++) {
            int tmp = nums[i];
            if (tmp == k) res++;
            for (int j = i + 1; j < n; j++) {
                tmp += nums[j];
                if (tmp == k) res++;
            }
        }
        return res;
    }

    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int res=0;
        Map<Integer,Integer> map=new HashMap<>();
        map.put(0,1);
        int pre=0;
        for(int i=0;i<n;i++){
            pre+=nums[i];
            res+=map.getOrDefault(pre-k,0);
            map.put(pre,map.getOrDefault(pre,0)+1);
        }
        return res;
    }
}
